package offer;

public class reversePairs_51 {
    //利用归并排序解答，在合并的时候，当左边的大于右边，就计算逆序数。
    //计算公式； mid-left+1
    //定义一个全局的计数器变量
    int count = 0;
    public int reversePairs(int[] nums) {
        this.count = 0;
        mergeSort(nums, 0, nums.length-1);
        return count;
    }
    public void mergeSort(int[] nums,int left,int right){
        //当只有一个节点的时候，直接返回，退出递归
        if(left >= right){
            return;
        }
        int mid = left + (right - left)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //合并
        merge(nums,left,mid,right);
    }
    public void merge(int[] nums,int left,int mid,int right){
        //定义一个临时数组
        int[] temp = new int[right-left+1];
        int i = left;
        int j = mid+1;
        int t = 0;
        while(i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                temp[t++] = nums[i++];
            }else{
                count += mid-i+1;
                temp[t++] = nums[j++];
            }
        }
        while(i <= mid){
            temp[t++] = nums[i++];
        }
        while(j <= right){
            temp[t++] =nums[j++];
        }
        for(int k =0; k< temp.length;k++){
            nums[left+k] = temp[k];
        }
    }


    private int count2 = 0;
    public int reversePairs2(int[] nums) {
        mergeSort2(nums,0, nums.length - 1);
        return count2;
    }

    public void mergeSort2(int[] nums,int left, int right){
        if(left >= right) return;
        int mid = left + (right - left)/2;
        mergeSort2(nums,left,mid);
        mergeSort2(nums,mid + 1,right);
        merge2(nums,left,mid,right);
    }

    public void merge2(int[] nums, int left, int mid, int right){
        int[] tmp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                tmp[t++] = nums[i++];
            }else{
                tmp[t++] = nums[j++];
                count2 += mid - i + 1;
            }
        }
        while (i <= mid){
            tmp[t++] = nums[i++];
        }
        while (j <= right){
            tmp[t++] = nums[j++];
        }
        for (int k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }


    }







}
